package listbyorder.access101_200.test135;

import java.util.Arrays;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/11 10:29
 */
public class Solution1 {

    // 分发糖果
    // 贪心策略_____正向遍历
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int len = ratings.length;
        int[] candies = new int[len];
        Arrays.fill(candies, 1);

        // 正向遍历
        for (int i = 0; i < len - 1; i++) {
            if (ratings[i] < ratings[i + 1]) {
                candies[i + 1] = candies[i] + 1;
            }
        }

        // 反向遍历
        for (int i = len - 1; i > 0; i--) {
            if (ratings[i] < ratings[i - 1]) {
                if(candies[i] >= candies[i - 1])
                candies[i - 1] = candies[i] + 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans += candies[i];
        }

        return ans;
    }
}
